package com.arrays.a2;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/*三角形最短路径
    [2]
    [3,4]
    [6,5,7]
    [4,1,8,3]
*/
public class MinimumTotal {

    /*
    从上往下
     */
    public static int minimumTotal(List<List<Integer>> triangle) {
        int len = triangle.size();
        // 新建二维数组
        int[][] dp = new int[len][len];
        //边界
        dp[0][0] = triangle.get(0).get(0);
        for (int i = 1; i < len; i++) {
            dp[i][0] = dp[i - 1][0] + triangle.get(i).get(0);
            for (int j = 1; j < i; j++) {
                dp[i][j] = Math.min(dp[i - 1][j - 1], dp[i - 1][j]) + triangle.get(i).get(j);
            }
            dp[i][i] = dp[i - 1][i - 1] + triangle.get(i).get(i);
        }
        //三角形最后一行的起始位置
        int ans = dp[len - 1][0];
        //遍历最后一行所有位置比较
        for (int i = 0; i < len; i++) {
            ans = Math.min(ans, dp[len - 1][i]);
        }
        return ans;
    }

    /*
    从下往上
     */
    public static int minimumTotal2(List<List<Integer>> triangle) {
        int n = triangle.size();
        int[][] dp = new int[n + 1][n + 1];
        for (int i = n - 1; i >= 0; i--) {
            for (int j = 0; j <= i; j++) {
                dp[i][j] = Math.min(dp[i + 1][j], dp[i + 1][j + 1]) + triangle.get(i).get(j);
            }
        }
        return dp[0][0];
    }

    /*
    减小空间复杂度
    一维数组
    */
    public static int minimumTotal3(List<List<Integer>> triangle) {
        int n = triangle.size();
        int[] dp = new int[n + 1];
        for (int i = n - 1; i >= 0; i--) {
            for (int j = 0; j <= i; j++) {
                dp[j] = Math.min(dp[j], dp[j + 1]) + triangle.get(i).get(j);
            }
        }
        return dp[0];
    }

    //triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
    public static void main(String[] args) {
        ArrayList<List<Integer>> lists = new ArrayList<>();
        ArrayList<Integer> list1 = new ArrayList<>();
        ArrayList<Integer> list2 = new ArrayList<>();
        ArrayList<Integer> list3 = new ArrayList<>();
        ArrayList<Integer> list4 = new ArrayList<>();

        list1.add(2);
        Collections.addAll(list2, 3, 4);
        Collections.addAll(list3, 6, 5, 7);
        Collections.addAll(list4, 4, 1, 8, 3);

        Collections.addAll(lists, list1, list2, list3, list4);
        System.out.println(lists);

        int i = minimumTotal3(lists);
        System.out.println(i);
    }
}
